package com.heima.leetcode.practice;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * leetcode 47. 全排列 II
 * @author 勾新杰
 * @version 1.0
 * @date 2024/11/14 17:19
 */
public class E47 {
    /*
    要能处理重复元素的排列，假如要对m个元素全排列，其中有n个重复元素，则公式：P(m,m)/P(n,n)
    原理就是保证这n个元素有序，所以可以考虑先把nums数组排序，然后进行排列的时候要保证有序
    这里就保证按照排序后出现的顺序进行排除就可以了
         1                   2                  2                   4
      /  |  \             /  |  \            /  |  \             /  |  \
     2   2   4          1   2   4          1   2   4           1   2   2
    /\  /\   /\        /\  /\   /\        /\  /\   /\         /\  /\   /\
   2 4 2 4  2 2       2 4 1 4  1 2       2 4 1 4  1 2        2 2 1 2  1 2
   | | | |  | |       | | | |  | |       | | | |  | |        | | | |  | |
   4 2 4 2  2 2       4 2 4 1  2 1       4 2 4 1  2 1        2 2 2 1  2 1
       x x    x                          x x x x  x x          x      x x

     P(4,4)/P(2,2) = 12 正确的
     */


    /**
     * 全排列
     * @param nums 数组
     * @return 全排列结果
     */
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
        dfs(nums, result, new LinkedList<>(), new boolean[nums.length]);
        return result;
    }

    /**
     * 回溯算法
     * @param nums 数组
     * @param result 结果集
     * @param currentPath 当前结果
     * @param visited 访问标记
     */
    private void dfs(int[] nums, List<List<Integer>> result, LinkedList<Integer> currentPath, boolean[] visited) {
        // 递归终止条件
        if (currentPath.size() == nums.length){
            result.add(new ArrayList<>(currentPath));
            return;
        }
        // 深度优先遍历每颗树
        for (int i = 0; i < nums.length; i++) {
            // 保证有序的方式进行剪枝
            if (i > 0 && nums[i] == nums[i - 1] && !visited[i - 1]) continue;
            // 递归深度优先遍历
            if (!visited[i]) {
                currentPath.push(nums[i]);
                visited[i] = true;
                dfs(nums, result, currentPath, visited);
                currentPath.pop(); // 回溯
                visited[i] = false; // 回溯
            }
        }
    }
}
